//剑指offer61，序列化二叉树

//请实现两个函数，分别用来序列化和反序列化二叉树

//二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，
//从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序
//的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
//，以 ！ 表示一个结点值的结束（value!）。

//二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

//例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树


//思路，序列化可以用队列来做，就是层序遍历，反序列化也是用队列，是前序遍历
//注意，两个函数之间没有联系，即序列化的结果不会用作反序列化的形参


import java.util.Queue;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        if(root!=null){ 
       sb.append(String.valueOf(root.val));
    Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            if(tmp.left!=null||tmp.right!=null){
            if(tmp.left!=null){
                sb.append(","+String.valueOf(tmp.left.val));
                queue.offer(tmp.left);
            }else{
                sb.append(",#");
            }
            if(tmp.right!=null){
                sb.append(","+String.valueOf(tmp.right.val));
                queue.offer(tmp.right);
            }else{
                sb.append(",#");
                }
            }
        }
    }  
        return sb.toString();
}
    
    TreeNode Deserialize(String str) {
       TreeNode root=null;
        if(!str.equals("")){
        String[] arr=str.split(",");
        root=new TreeNode(Integer.parseInt(arr[0]));
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int index=1;
        while(!queue.isEmpty()&&index<arr.length){
            TreeNode cur=queue.poll();
            if(index<arr.length&&!arr[index].equals("#")){
                cur.left=new TreeNode(Integer.parseInt(arr[index]));
                index++;
                queue.offer(cur.left);
            }else{
                index++;
            }
            if(index<arr.length&&!arr[index].equals("#")){
                cur.right=new TreeNode(Integer.parseInt(arr[index]));
                index++;
                queue.offer(cur.right);
            }else{
                index++;
            }
        }
    }
      return root;
    }
}